package acwing;

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;



public class A850P2 {
static int N=150010;
  static  BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
  static  BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
static int[] h=new int[N];
static int[] e=new int[N];
static int[] ne=new int[N];
static int[] w=new int[N];//边权
static int idx=1;
static boolean[] st=new boolean[N];
static int[] dist=new int[N];
static int n;
static int m;
static PriorityQueue<int[]> queue=new PriorityQueue<>((a,b)->{return a[0]-b[0];});//小根堆
    static int dijkstar(){
        Arrays.fill(dist, 0x3f3f3f3f);
        //将原点加入队列
        dist[1]=0;
        queue.offer(new int[]{0,1});//{离原点距离，点的编号}
        //更新原点的最短路
        while(!queue.isEmpty()){
            int[] poll = queue.poll();
            int distance=poll[0];
            int ver=poll[1];//点
            if(st[ver])continue;//跳过那些重复的点但是距离比较大的
            st[ver]=true;  //ver第一次被取出，也标志着他的最短距离确定了
            for(int edge=h[ver];edge!=0;edge=ne[edge]){
                int end=e[edge];
                if(dist[end]>distance+w[edge])
                //更新距离
                {
                    dist[end]=distance+w[edge];
                    //加入优先队列
                    queue.offer(new int[]{dist[end],end});//end可能会被多次更新，也就是小根堆里面会有多个(end离原点的距离，点的编号end)
             //那么距离最小的那个会先被拿出来，并且st[ver]
                }
            }
        }
        //当优先队列不为空，取出优先队列头节点，如果该点的最小距离还未被确定
        // ，此时，对他最小距离产生影响的点已经被处理了
        //标记该点已确定最短距离
        //对以他为起点的边的终点的最小值进行修改
return dist[n]==0x3f3f3f3f?-1:dist[n];
    }
    //添加带权边
    static void add(int a,int b,int c){
        e[idx]=b;
        w[idx]=c;
        ne[idx]=h[a];
        h[a]=idx++;
    }
    public static void main(String[] args) throws IOException {
        String[] s = read.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);

        while (m-- > 0) {
            String[] edge = read.readLine().split(" ");
            int x = Integer.parseInt(edge[0]);
            int y = Integer.parseInt(edge[1]);
            int c = Integer.parseInt(edge[2]);
            add(x, y, c);
        }
        int res=dijkstar();
log.write(Integer.toString(res));
log.flush();
        //输入
    }
}
